module Alg where

import Data.Graph.Inductive.Graph (Node,nodes,neighbors)
import Data.Graph.Inductive.Tree (UGr)
import Utils(compl,maxList)
import List(intersect,delete,elem)

findAllCliques:: UGr -> [Node]
findAllCliques graph = expand vertices vertices [] [] where
    vertices = nodes graph
    -- depth-first search in tree of cliques	
    expand :: [Node] -> [Node] -> [Node] -> [Node] -> [Node]
    expand [] _ q leader = maxList q leader
    -- q - current clique, leader - the largest clique has been found
    expand subgraph candidates q leader = examineCand difference candidates q leader
        where
        difference :: [Node]
        difference = [x|x<-candidates,not $ elem x neighbourhood]
        --N(u), with u: vertex in SUBG which maximizes |intersection(CAND, N(u))|
        neighbourhood :: [Node]
        neighbourhood = foldl (\ tempMax -> 
            maxList tempMax . (intersect candidates) . neighbors graph) [] subgraph
        --while ((CAND \ N(u)) != []) research N(u)
        examineCand :: [Node] -> [Node] -> [Node] -> [Node] -> [Node]		
        examineCand [] _ _ leader = leader
        examineCand (d:diff) cand q leader = examineCand diff reducedCand q $! subtreeLeader
            where
                neighD = neighbors graph d
                reducedCand = delete d cand
                --find maximal cliques in the subtree of <d>
                subtreeLeader = (expand (intersect neighD subgraph) (intersect neighD cand) (d:q) leader)

--find the largest of all found maximal independebt sets
findMaxIndSet:: UGr -> [Node]
findMaxIndSet gr = findAllCliques $ compl gr